//最接近原点的 K 个点
/*给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
1 <= k <= points.length <= 104
-10^4 < xi, yi < 10^4
*/
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */

struct new_date {
    int x;
    int y;
    double z;
};

typedef struct new_date date;
int compare(const void* q1, const void* q2) {
    return ((((date*)q1)->z) > (((date*)q2)->z));
}
int** kClosest(int** points, int pointsSize, int* pointsColSize, int k,
               int* returnSize, int** returnColumnSizes) {
    int** arr = (int**)malloc(sizeof(int*) * k);
    int size = 0;
    date* new_points = (date*)calloc(sizeof(date), pointsSize);
    for (int i = 0; i < pointsSize; i++) {
        new_points[i].x = points[i][0];
        new_points[i].y = points[i][1];
        new_points[i].z =
            sqrt(points[i][0] * points[i][0] + points[i][1] * points[i][1]);
    }
    // 找到符合条件的数组
    qsort(new_points, pointsSize, sizeof(date), compare);
    for (int i = 0; i < k; i++) {
        int* new = (int*)malloc(sizeof(int) * 2);
        new[0] = new_points[i].x;
        new[1] = new_points[i].y;
        arr[i] = new;
    }
    int* numsSize = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++) {
        numsSize[i] = 2;
    }
    *returnColumnSizes = numsSize;
    *returnSize = k;
    return arr;
}

//统计前后缀下标对 I
/*给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

当 str1 同时是 str2 的前缀（
prefix
）和后缀（
suffix
）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。
例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

 1 <= words.length <= 50
1 <= words[i].length <= 10
words[i] 仅由小写英文字母组成。
*/
bool isPrefixAndSuffix(char* str1, char* str2) {
    int size1 = strlen(str1);
    int size2 = strlen(str2);
    if (size1 > size2)
        return false;
    for (int i = 0; i < size1; i++) {
        if (str1[i] != str2[i])
            return false;
    }
    for (int i = size1 - 1; i >= 0; i--, size2--) {
        if (str1[i] != str2[size2 - 1])
            return false;
    }
    return true;
}
int countPrefixSuffixPairs(char** words, int wordsSize) {
    int count = 0;
    for (int i = 0; i < wordsSize; i++) {
        for (int j = i + 1; j < wordsSize; j++) {
            if (isPrefixAndSuffix(words[i], words[j]))
                count++;
        }
    }
    return count;
}